/*
 * @Author: szx
 * @Date: 2022-05-19 13:18:14
 * @LastEditTime: 2022-05-19 13:41:38
 * @Description:
 * @FilePath: \leetcode\400-499\462\462.js
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
// var minMoves2 = function (nums) {
//     nums.sort((a, b) => a - b);
//     const n = nums.length;
//     let res = 0,
//         x = nums[Math.floor(n / 2)];
//     for (let i = 0; i < n; i++) {
//         res += Math.abs(nums[i] - x);
//     }
//     return res;
// };

var minMoves2 = function (nums) {
    let n = nums.length,
        // x就是中位数
        x = quickSelect(nums, 0, n - 1, Math.floor(n / 2)),
        ret = 0;
    for (let i = 0; i < n; ++i) {
        ret += Math.abs(nums[i] - x);
    }
    return ret;
};

const quickSelect = (nums, left, right, index) => {
    const rp = Math.floor(Math.random() * (right - left + 1)) + left;
    swap(nums, rp, right);
    let x = nums[right],
        i = left;
    for (let j = left; j < right; ++j) {
        if (nums[j] <= x) {
            swap(nums, i, j);
            i++;
        }
    }
    swap(nums, i, right);
    if (i === index) {
        return nums[i];
    } else {
        return i < index ? quickSelect(nums, i + 1, right, index) : quickSelect(nums, left, i - 1, index);
    }
};

const swap = (nums, index1, index2) => {
    const temp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = temp;
};
